package com.HeJing.数组的相关算法操作;

/**
 * ClassName: 数组相关排序操作
 * Package: com.HeJing.数组的相关算法操作
 * Description:
 *
 * @Author: HeJing
 * @Create: 2023-03-19 19:03
 * @Version: 1.0
 */
public class 数组相关排序操作 {
    public static void main(String[] args){
        /*
        *   注1: 常见算法的时间复杂度由小到大依次为: O(1) < O(log2n) < O(nlog2n) < O(n2) < O(n3) < ... < O(2n)
        *
        *   1、排序算法分类: 内部排序、外部排序
        *       -> 内部排序: 整个排序过程不需要借助于外部储存器(比如磁盘等)，所有的排序操作都在内存中完成
        *       -> 外部排序: 参与排序的数据非常多，数据量非常大，计算级必须借助于外部储存器(如磁盘等)。外部排序最常见的是
        *           多路归并排序，可以认为外部排序是由多次内部排序组成。
        *
        *   2、十大内部排序算法:
        *       -> 插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序、桶排序、基数排序
        *       -> 开发中默认使用的排序方式: 快排
        * */

        test();
    }

    public static void test(){

        // 冒泡排序测试:
        // bubbleSortTest();

        // 快速排序测试:
        quickSortTest();
    }

    // 打印函数:
    public static void printArr(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            System.out.print(arr[i] + "\t");
        }
        System.out.println(arr[arr.length - 1]);
    }

    // 冒泡排序测试:
    public static void bubbleSortTest(){
        int[] arr1 = new int[10];
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = (int)(Math.random() * (100 - 10 + 1)) + 10;  // 数组元素取值范围: 10-100
        }

        // 排序前打印:
        System.out.print("进行冒泡排序之前的数组: ");
        printArr(arr1);

        // 进行排序操作:
        bubbleSort(arr1);

        // 排序后打印：
        System.out.print("进行冒泡排序之后的数组:  ");
        printArr(arr1);
    }

    // 冒泡排序具体算法实现
    public static void bubbleSort(int[] arr1){
        for (int i = 0; i < arr1.length - 1; i++) {
            for(int j = 0; j < arr1.length - 1 - i; j++){
                if(arr1[j] > arr1[j + 1]){
                    int temp = arr1[j];
                    arr1[j] = arr1[j + 1];
                    arr1[j + 1] = temp;
                }
            }
        }
    }

    // 快速排序测试:
    public static void quickSortTest(){
        int[] arr2 = {9, 13, 32, 23, -320, 23, 133, 973, 22};
        System.out.print("快速排序之前: ");
        printArr(arr2);

        // 进行快速排序操作:
        quickSort(arr2);

        System.out.print("快速排序之后: ");
        printArr(arr2);
    }

    // 快速排序具体算法实现:
    public static void quickSort(int[] arr){
        subSort(arr, 0, arr.length - 1);
    }

    public static void subSort(int[] arr, int start, int end){
        if(start < end){
            int base = arr[start];
            int low = start;
            int high = end + 1;

            while(true){
                while(low < end && arr[++low] - base <= 0)
                    ;
                while(high > start && arr[--high] - base >= 0)
                    ;
                if(low < high){
                    // 交换arr数组[low] 与 [high] 位置的元素
                    swap(arr, low, high);
                }else{
                    break;
                }
            }
            // 交换arr数组[start] 与 [high] 位置的元素
            swap(arr, start, high);   // 实际上，此时，low == high
            // 经过代码[start, high)部分的元素比[high, end)的都小

            // 经过递归调用，对arr数组[start,high-1]部分重复以上过程
            subSort(arr, start, high - 1);

            // 通过递归掉用，对arr数组[high+1, end)部分元素重复以上过程
            subSort(arr, high + 1, end);

        }
    }

    // 数组某两个位置的元素进行交换操作
    public static void swap(int[] arr, int start, int end){
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
}

















